//
// Description: 102. 二叉树的层序遍历
// Created by Loading on 2021/5/14.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> vec_levelOrder;
    //维护一个队列
    queue<TreeNode *> q;
    //根节点首先入队列
    if (root) {
        q.emplace(root);
    }

    while (!q.empty()) {
        //每一层的节点数量
        int size = q.size();
        vector<int> vec;

        while (size-- > 0) {
            TreeNode *treeNode = q.front();
            vec.emplace_back(treeNode->val);
            //下一层节点入队列
            if (treeNode->left) {
                q.emplace(treeNode->left);
            }
            if (treeNode->right) {
                q.emplace(treeNode->right);
            }
            //本层节点出队列
            q.pop();
        }
        vec_levelOrder.emplace_back(vec);
    }

    return vec_levelOrder;
}

int main() {
    auto *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    vector<vector<int>> vec_levelOrder;
    vec_levelOrder = levelOrder(root);
    for (auto &v : vec_levelOrder) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
    cout << endl;
}